// 节点类
class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

// 双向链表类
class DoublyLinked {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  toString() {
    return this.forwardString();
  }

  // 正向遍历
  forwardString() {
    let now = this.head, res = '';
    while (now) {
      res += now.value + ' ';
      now = now.next;
    }
    return res;
  }

  // 反向遍历
  backwardString() {
    let now = this.tail, res = '';
    while (now) {
      res += now.value + ' ';
      now = now.prev;
    }
    return res;
  }

  // 从后面追加
  append(value) {
    let newNode = new Node(value);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  // 插入某位置
  insert(index, value) {
    if (index > this.length || index < 0)
      return false;
    if (this.length === index) {
      this.append(value);
    } else {
      let newNode = new Node(value);
      if (index === 0) {
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
      } else {
        let now = this.find(index);
        newNode.prev = now.prev;
        newNode.next = now;
        now.prev.next = newNode;
        now.prev = newNode;
      }
      this.length++;
    }
    return true;
  }

  // 寻找某位置节点
  find(index) {
    let now;
    if (this.length / 2 > index) {
      now = this.head;
      for (let i = 0; i < index; i++)
        now = now.next;
    } else {
      now = this.tail;
      for (let i = this.length - 1; i > index; i--)
        now = now.prev;
    }
    return now;
  }

  // 获取某位置元素
  get(index) {
    if (index >= this.length || index < 0) {
      return null;
    } else {
      return this.find(index).value;
    }
  }

  // 查找某元素位置
  indexOf(value) {
    for (let i = 0, now = this.head; i < this.length; i++, now = now.next) {
      if (now.value === value)
        return i;
    }
    return -1;
  }

  // 更新某位置元素
  update(index, value) {
    if (index >= this.length || index < 0) {
      return null;
    } else {
      let now = this.find(index);
      let res = now.value;
      now.value = value;
      return res;
    }
  }

  // 删除某位置元素
  removeAt(index) {
    if (index < 0 || index >= this.length)
      return null;
    let res;
    if (this.length === 1) {
      res = this.head.value;
      this.head = null;
      this.tail = null;
    } else {
      if (index === 0) {
        res = this.head.value;
        this.head.next.prev = null;
        this.head = this.head.next;
      } else if (index === this.length - 1) {
        res = this.tail.value;
        this.tail.prev.next = null;
        this.tail = this.tail.prev;
      } else {
        let now = this.find(index);
        res = now.value;
        now.next.prev = now.prev;
        now.prev.next = now.next;
      }
    }
    this.length--;
    return res;
  }

  // 删除某元素
  remove(value) {
    return this.removeAt(this.indexOf(value));
  }

  // 判断是否为空
  isEmpty() {
    return thsi.length === 0;
  }

  // 链表长度
  size() {
    return this.length;
  }
}

module.exports = DoublyLinked;
